package com.ly.algorithm.offerpointer;

import java.util.ArrayDeque;
import java.util.LinkedList;
import java.util.Queue;

/**
 * @Classname Offer37
 * @Description
 *
 * 请实现两个函数，分别用来序列化和反序列化二叉树。
 *
 * 示例: 
 *
 * 你可以将以下二叉树：
 *
 *     1
 *    / \
 *   2   3
 *      / \
 *     4   5
 *
 * 序列化为 "[1,2,3,null,null,4,5]"
 *
 *
 * @Date 2021/1/30 14:41
 * @Author 冷心影翼
 */
public class Offer37 {

    public static void main(String[] args) {
        Codec codec = new Codec();
        String serialize = codec.serialize(TreeNode.init(new int[]{1,2,3,-1,-1,4,5}));
        System.out.println(serialize);
        TreeNode deserialize = codec.deserialize(serialize);
        deserialize.preOrder(deserialize);
    }
}

class Codec {

    StringBuilder sb;

    // Encodes a tree to a single string.
    public String serialize(TreeNode root) {
        sb = new StringBuilder();
        if(root == null) {
            return "";
        }
        Queue<TreeNode> queue = new LinkedList<>();
        queue.add(root);
        while (!queue.isEmpty()) {
            TreeNode poll = queue.poll();
            if(poll == null) {
                sb.append("#,");
            }else {
                sb.append(poll.val+",");
                queue.add(poll.left);
                queue.add(poll.right);
            }
        }
        return sb.toString().substring(0,sb.length()-1);
    }



    // Decodes your encoded data to tree.
    public TreeNode deserialize(String data) {
        String[] split = data.split(",");
        if(split.length == 0 || data.equals("")) {
            return null;
        }
        TreeNode root = new TreeNode(Integer.parseInt(split[0]));
        Queue<TreeNode> queue = new LinkedList<>();
        queue.add(root);
        int i = 1;
        while (true) {
            if(i>=split.length) {
                break;
            }
            TreeNode poll = queue.poll();
            if(split[i].equals("#")) {
                poll.left = null;
            }else {
                poll.left = new TreeNode(Integer.parseInt(split[i]));
                queue.add(poll.left);
            }
            i++;
            if(split[i].equals("#")) {
                poll.right = null;
            }else {
                poll.right = new TreeNode(Integer.parseInt(split[i]));
                queue.add(poll.right);
            }
            i++;
        }
        return root;
    }
}